//package com.xinheyun.demo.leetcode;
//
//import java.util.ArrayList;
//import java.util.Arrays;
//
///**
// * @description: TODO
// * @author: Sarah
// * @modified By: Sarah
// * @date: Created in 2021/8/30 9:37
// * @version:v1.0 //
// */
////
////给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。
////
////    例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。
////
////    也就是说，选取下标 i 的概率为 w[i] / sum(w) 。
////
////     
////
////    示例 1：
////
////    输入：
////    ["Solution","pickIndex"]
////    [[[1]],[]]
////    输出：
////    [null,0]
////    解释：
////    Solution solution = new Solution([1]);
////    solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。
////    示例
////
////    来源：力扣（LeetCode）
////    链接：https://leetcode-cn.com/problems/random-pick-with-weight
////    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//
//public class test528 {
//
//    int index = 0;
//    int[] w1;
//
//    public static void main(String[] args) {
//        int a[] ={3,14,1,7};
//        test528 test528 = new test528(a);
//        for(int i=0;i<10;i++){
//            System.out.println(test528.pickIndex());
//        }
//    }
//
//    public test528(int[] w) {
//        ArrayList<Integer> integers = new ArrayList<>();
//        for (int i = 0; i < w.length; i++) {
//            for (int j = 0; j < w[i]; j++) {
//                integers.add(i);
//            }
//        }
//        w1 = new int[integers.size()];
//        for (int i = 0; i < integers.size(); i++) {
//            w1[i] = integers.get(i);
//        }
//    }
//
//    public int pickIndex() {
//        if (index > w1.length) {
//            index = 0;
//        }
//        return w1[index++];
//    }
//
//
//class Solution528 {
//    int[] pre;
//    int total;
//
//    public Solution528(int[] w) {
//        pre = new int[w.length];
//        pre[0] = w[0];
//        for (int i = 1; i < w.length; ++i) {
//            pre[i] = pre[i - 1] + w[i];
//        }
//        total = Arrays.stream(w).sum();
//    }
//
//    public int pickIndex() {
//        int x = (int) (Math.random() * total) + 1;
//        return binarySearch(x);
//    }
//
//    private int binarySearch(int x) {
//        int low = 0, high = pre.length - 1;
//        while (low < high) {
//            int mid = (high - low) / 2 + low;
//            if (pre[mid] < x) {
//                low = mid + 1;
//            } else {
//                high = mid;
//            }
//        }
//        return low;
//    }
//}